import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class BubbleSort {

    private static final int[] arr = new int[]{5, 7, 3, 4, 1, 6, 2, 8, 9};
    private static final int[] arr2 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
    private static final int[] arr3 = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
    private static final int[] demo = new int[]{5, 2, 7, 4, 1, 3, 8, 9};

    private static void swapCount(int i, int j) {
        System.out.printf("第 %d 轮, 第 %d 次比较\n", i + 1, j);
    }

    private static void swapAfter(int[] arr, int i) {
        System.out.printf("第 %d 轮后: %s\n\n", i + 1, Arrays.toString(arr));
    }

    public static void swap(int[] arr, int i, int j) {
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
    }


    /**
     * 外层就控制指针, 最差的写法, 一般还写不出来这么差的
     */
    @Test
    public void bubble() {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
                swapCount(i, j + 1);
            }
            swapAfter(arr, i);
        }
    }


    /**
     * 减少内层重复比较次数
     */
    @Test
    public void bubble1_1() {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
                swapCount(i, j + 1);
            }
            swapAfter(arr, i);
        }
    }


    @Test
    public void bubble1_2() {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                }
                swapCount(i, j - i);
            }
            swapAfter(arr, i);
        }
    }


    /**
     * 减少无效比较次数, 如果有序了, 还需要再比较一次
     */
    @Test
    public void bubble2() {
        int[] arr = BubbleSort.arr;
        for (int i = 0; i < arr.length - 1; i++) {
            boolean swapped = false;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                    swapped = true;
                }
                swapCount(i, j - i);
            }
            swapAfter(arr, i);
            if (!swapped) {
                break;
            }
        }
    }

    /**
     * 减少无效比较次数, 如果有序了直接返回
     */
    @Test
    public void bubble2_2() {
        int[] arr = BubbleSort.arr2;
        int n = arr.length - 1;
        for (int j = 0; n != 0; j++) {
            int last = 0; // 最后一次索引交换位置
            for (int i = 0, k = 1; i < n; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    last = i;
                    // System.out.println(i);
                    swapCount(j, k++);
                }
            }
            n = last;
            swapAfter(arr, j);
        }
    }

    @Test
    public void bubble2_demo() {
        int[] arr = new int[]{5, 7, 3, 4, 1, 6, 2, 8, 9};

        int n = arr.length - 1;

        while (n != 0) {
            int last = 0; // 最后一次索引交换位置

            for (int i = 0; i < n; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                    last = i;
                }
            }
            n = last;
        }

        System.out.println(Arrays.toString(arr));
    }
}
